package string;

import java.util.Arrays;

/**
 * 1443.Longest common subsequence 最长公共子序列
 *
 Given two strings text1 and text2,
 return the length of their longest common subsequence.

 A subsequence of a string is a new string generated
 from the original string with some characters(can be none) deleted
 without changing the relative order of the remaining characters.
 (eg, "ace" is a subsequence of "abcde" while "aec" is not).
 A common subsequence of two strings is a subsequence that is common to both strings.

 If there is no common subsequence, return 0.

 Example 1:

 Input: text1 = "abcde", text2 = "ace"
 Output: 3
 Explanation: The longest common subsequence is "ace" and its length is 3.
 Example 2:

 Input: text1 = "abc", text2 = "abc"
 Output: 3
 Explanation: The longest common subsequence is "abc" and its length is 3.
 Example 3:

 Input: text1 = "abc", text2 = "def"
 Output: 0
 Explanation: There is no such common subsequence, so the result is 0.


 Constraints:

 1 <= text1.length <= 1000
 1 <= text2.length <= 1000
 */
public class Q1143_LongestCommonSubse {
    /**
     * do
     * two-dimensional array
     */
    private int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        // define state, represent the longest-common-subsequence length
        int[][] dp = new int[len1+1][len2+1];
        // initialize
        // equation of state transition
        // dp[i][j] = dp[i-1][j-1] + 1; dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    //likely, [0,i-1] [0,j]; [0,i] [0,j-1] 的最长公共子序列的长度
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        /*
         0  1  2  3 j
      0 [0, 0, 0, 0]
      1 [0, 1, 1, 1]
      2 [0, 1, 1, 1]
      3 [0, 1, 2, 2]
      4 [0, 1, 2, 2]
      5 [0, 1, 2, 3]
      i  */
        for (int i=0; i<text1.length()+1; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[len1][len2];
    }

    /**
     * one-dimensional array
     */
    private int longestCommonSubsequenceOne(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[] dp = new int[len2+1];
        for (int i=1; i<=len1; i++) {
            int last = 0; //left-up: dp[i-1][j-1]
            for (int j=1; j<=len2; j++) {
                int tmp = dp[j]; //must record the value of last element
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[j] = last + 1;
                } else {
                    int up = dp[j]; //up: dp[i-1][j]
                    int left = dp[j-1]; //left: dp[i][j-1]
                    dp[j] = Math.max(left, up);
                }
                last = tmp;
            }
        }
        /*
        abcde i
        ace j
        [0, 0, 0, 0] //初始状态
        t1[0] == t2[0] // dp[1] = last + 1 = 1; last = d[1]
        t1[0] != t2[1] // left=d[2-1] up=dp[2] dp[2] = Math.max(left, up);
         */
        System.out.println(Arrays.toString(dp));
        return dp[len2];
    }

    public static void main(String[] args) {
        // bsbininm jmjkbkjkv
        // abcde ace
        // pmjghexybyrgzczy hafcdqbgncrcbihkd
        String text1 = "pmjghexybyrgzczy";
        String text2 = "hafcdqbgncrcbihkd";
        Q1143_LongestCommonSubse q1143_longestCommonSubse = new Q1143_LongestCommonSubse();
        int res = q1143_longestCommonSubse.longestCommonSubsequence(text1, text2);
        System.out.println(res);
        int res1 = q1143_longestCommonSubse.longestCommonSubsequenceOne(text1, text2);
        System.out.println(res1);
    }
}
